public class Exercise1_3_31<Item> {
    // 双向列表类

    private DoubleNode first;  // 表头
    private DoubleNode last;  // 表尾
    private class DoubleNode{
        Item item;
        DoubleNode prev;  // 上一个节点
        DoubleNode next;  // 下一个节点
    }

    // 在表头添加节点
    public void addAtTop(Item item){
        DoubleNode oldfirst = first;
        first = new DoubleNode();
        first.item = item;
        first.prev = null;
        first.next = oldfirst;
        if (oldfirst != null){
            oldfirst.prev = first;
        }else{
            last = first;
        }
    }

    // 在表尾添加节点
    public void addAtEnd(Item item){
        DoubleNode oldlast = last;
        last = new DoubleNode();
        last.item = item;
        last.prev = oldlast;
        last.next = null;
        if (oldlast != null){
            oldlast.next = last;
        }else{
            first = last;
        }
    }

    // 在表头删除节点
    public Item deAtTop(){
        Item item = first.item;
        first = first.next;
        first.prev = null;
        return item;
    }

    // 在表尾删除节点
    public Item deAtEnd(){
        Item item = last.item;
        last = last.prev;
        last.next = null;
        return item;
    }

    // 在指定节点之前插入新节点
    public void insertBefore(Item item, Item newItem){
        DoubleNode x = findNode(item);
        if (x != null){
            DoubleNode newNode = new DoubleNode();
            newNode.item = newItem;
            newNode.prev = x.prev;
            newNode.next = x;
            if (x.prev != null){
                x.prev.next = newNode;
            }else{
                first = newNode;
            }
            x.prev = newNode;
        }
        else{
            System.out.println("未找到指定节点");
        }
    }

    // 在指定节点之后插入新节点
    public void insertAfter(Item item, Item newItem){
        DoubleNode x = findNode(item);
        if (x != null){
            DoubleNode newNode = new DoubleNode();
            newNode.item = newItem;
            newNode.prev = x;
            if (x.next != null){
                newNode.next = x.next;
                x.next.prev = newNode;
            }else{
                last = newNode;
            }
            x.next = newNode;
        }else{
            System.out.println("未找到指定节点");
        }
    }
    // 删除指定节点
    public void delete(Item item){
        DoubleNode x = findNode(item);
        if (x != null){
            x.prev.next = x.next;
            x.next.prev = x.prev;
        }else{
            System.out.println("未找到指定节点");
        }
    }

    // 查找某个节点
    public DoubleNode findNode(Item item){
        for  (DoubleNode x = first; x != null; x = x.next){
            if (x.item == item){
                return x;
            }
        }
        return null;
    }

    public void print(){
        System.out.println("------------");
        for  (DoubleNode x = first; x != null; x = x.next){
            System.out.print(x.item + ", ");
        }
        System.out.println();
        for  (DoubleNode x = last; x != null; x = x.prev){
            System.out.print(x.item + ", ");
        }
        System.out.println();
        System.out.println("------------");
        System.out.println();

    }

    public static void main(String args[]){
        String[] strings = {"1", "2", "3", "4", "5"};

        Exercise1_3_31<String> lined_list = new Exercise1_3_31<>();
        for (String a : strings){
            lined_list.addAtEnd(a);
        }
        lined_list.print();

        lined_list.deAtEnd();
        lined_list.print();

        lined_list.deAtTop();
        lined_list.print();

        lined_list.insertBefore("2", "1");
        lined_list.print();

        lined_list.insertAfter("4", "5");
        lined_list.print();

        lined_list.delete("3");
        lined_list.print();

        lined_list.delete("8");


    }
}
